package com.it.homework1;

public class Test1 {

    /**
     * 题目描述:
     * 给定一个字符串 s，找到其中最长的不含重复字符的子串的长度。
     *
     * 示例:
     * 输入: "abcabcbb"
     * 输出: 3
     * 解释: 无重复字符的最长子串是 "abc"，其长度为 3。
     *
     */
    public static void main(String[] args) {

        System.out.println(lengthOfLongestSubstring("abcabcdebcb"));
    }

    /**
     * 计算给定字符串中最长无重复字符的子串长度
     *
     * @param s 输入的字符串
     * @return 最长无重复字符子串的长度
     */
    public static int lengthOfLongestSubstring(String s) {
        // 字符串长度
        int n = s.length();
        // 最长无重复字符子串的长度初始化为0
        int maxLength = 0;
        // 左指针，用于标记无重复字符子串的起始位置
        int left = 0;
        // 存储每个字符最近一次出现的位置，初始化为0
        int[] charIndex = new int[128]; // ASCII 字符集

        // 遍历字符串中的每个字符（自己Debug一下）
        for (int right = 0; right < n; right++) {
            // 获取当前字符
            char c = s.charAt(right);

            // 更新左指针位置，确保无重复字符
            left = Math.max(charIndex[c], left);

            // 更新最长无重复字符子串的长度
            maxLength = Math.max(maxLength, right - left + 1);

            // 记录当前字符的最新位置
            charIndex[c] = right + 1;
        }

        // 返回最长无重复字符子串的长度
        return maxLength;
    }
}
